<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>stock</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="stock">stock</h1>
<h1 id="1-tushare-roy">1. tushare roy</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=oDhu5uGq_ic&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=20">https://www.youtube.com/watch?v=oDhu5uGq_ic&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=20</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/StockBuySellKTransactions.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/StockBuySellKTransactions.java</a></li>
</ul>
<h2 id="11-first-solution-onnk">1.1 first solution O(n<em>n</em>k)</h2>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp12a.png" alt="dp12a.png"></p>
<p>会超时</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, k: int, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        <span class="hljs-keyword">if</span> k &gt;= n // <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> sum([i - j <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> zip(prices[<span class="hljs-number">1</span>:], prices[:<span class="hljs-number">-1</span>]) <span class="hljs-keyword">if</span> i &gt; j])
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                dp[i][j] = dp[i][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, j):
                    dp[i][j] = max(dp[i][j], prices[j<span class="hljs-number">-1</span>] - prices[r<span class="hljs-number">-1</span>] + dp[i<span class="hljs-number">-1</span>][r])
                    
        <span class="hljs-keyword">return</span> dp[k][n]
</div></code></pre>
<p>这里最开始我还犯了一个错误。 写成了下面这样，看了好久才看出错误来</p>
<pre><code>for j in range(1, n+1):
    for r in range(1, j):
        dp[i][j] = max(dp[i][j-1], prices[j-1] - prices[r-1] + dp[i-1][r])
</code></pre>
<h2 id="12-second-solution-onk">1.2 second solution  O(n*k)</h2>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp12b.png" alt="dp12b.png"></p>
<p>每次loop， 对确定的i,j 来说， 因为 prices[j-1]不会变化， 我们只需要求  dp[i-1][j] - prices[j-1]的最大值就好了。 用一个maxdif来记录</p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp12c.png" alt="dp12c.png"></p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, k: int, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        <span class="hljs-keyword">if</span> k &gt;= n // <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> sum([i - j <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> zip(prices[<span class="hljs-number">1</span>:], prices[:<span class="hljs-number">-1</span>]) <span class="hljs-keyword">if</span> i &gt; j])
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            maxdif = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                dp[i][j] = max(dp[i][j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
                maxdif = max(maxdif, dp[i<span class="hljs-number">-1</span>][j] - prices[j<span class="hljs-number">-1</span>])
                    
        <span class="hljs-keyword">return</span> dp[k][n]
    
</div></code></pre>
<p>有一个有趣的现象， 上面的代码中， dp[i][j] 和maxdif的迭代运算可以交换位置， 不影响最后的答案!  为啥？</p>
<pre><code class="language-python"><div>        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            maxdif = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                maxdif = max(maxdif, dp[i<span class="hljs-number">-1</span>][j] - prices[j<span class="hljs-number">-1</span>])
                dp[i][j] = max(dp[i][j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
</div></code></pre>
<p>以  i=2, j=3 为例, 按照solution 1.1, m=0,1,2</p>
<ul>
<li>m=0   Prices(3) - Prices(0) + dp[1][0]</li>
<li>m=1   Prices(3) - Prices(1) + dp[1][1]</li>
<li>m=2   Prices(3) - Prices(2) + dp[1][2]</li>
</ul>
<p>如果把maxdif的迭代运算放到dp[i][j] 之前，相当于</p>
<pre><code>maxdif = max(dif, dp[1][3] - Prices(3))
dp[i][j] = max(dp[i][j-1], Prices(3) - Prices(3) + dp[i-1][j])
</code></pre>
<p>这没有意义， 这种情况下 maxdif不会更新, 还是原来的值, dp[i][j]也不会更新。</p>
<h1 id="2-labuladong的解法">2. labuladong的解法</h1>
<ul>
<li>
<p><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tuan-mie-gu-piao-wen-ti">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tuan-mie-gu-piao-wen-ti</a></p>
<pre><code>  # dp_with_stock[k][i]    = max(dp_with_stock[k][i-1], dp_without_stock[k-1][i-1] - PRICES[i])
  # dp_without_stock[k][i] = max(dp_without_stock[k][i-1], dp_with_stock[k][i-1] + PRICES[i])
</code></pre>
</li>
</ul>
<p>leetcode</p>
<ul>
<li>
<ol start="121">
<li>Best Time to Buy and Sell Stock       买1次</li>
</ol>
</li>
<li>
<ol start="122">
<li>Best Time to Buy and Sell Stock II    不限次数，买任意次</li>
</ol>
</li>
<li>
<ol start="123">
<li>Best Time to Buy and Sell Stock III   买2次</li>
</ol>
</li>
<li>
<ol start="188">
<li>Best Time to Buy and Sell Stock IV    买k次</li>
</ol>
</li>
<li>
<ol start="309">
<li>Best Time to Buy and Sell Stock with Cooldown  买k次，有cooldown, sell之后要间隔至少一天才能继续buy</li>
</ol>
</li>
<li>
<ol start="714">
<li>Best Time to Buy and Sell Stock with Transaction Fee</li>
</ol>
</li>
</ul>
<h2 id="121-best-time-to-buy-and-sell-stock-买1次">121. Best Time to Buy and Sell Stock       买1次</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock/</a></li>
</ul>
<p>tushare roy解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        m = len(prices)
        n = <span class="hljs-number">1</span>
        dp = [[<span class="hljs-number">0</span>] * (m+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            maxdif = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
                dp[i][j] = max(dp[i][j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
                maxdif = max(maxdif, dp[i<span class="hljs-number">-1</span>][j] - prices[j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> dp[n][m]
</div></code></pre>
<p>labuladong 解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        k = <span class="hljs-number">1</span>
        n = len(prices)
        dp0 = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>+k)]           <span class="hljs-comment"># without stock </span>
        dp1 = [[-float(<span class="hljs-string">'inf'</span>)] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>+k)] <span class="hljs-comment"># with stock</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                dp0[i][j] = max(dp0[i][j<span class="hljs-number">-1</span>], dp1[i][j<span class="hljs-number">-1</span>] + prices[j<span class="hljs-number">-1</span>])
                dp1[i][j] = max(dp1[i][j<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] - prices[j<span class="hljs-number">-1</span>])
                    
        <span class="hljs-keyword">return</span> dp0[k][n]
    
</div></code></pre>
<h2 id="122-best-time-to-buy-and-sell-stock-ii-不限次数买任意次">122. Best Time to Buy and Sell Stock II    不限次数，买任意次</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/</a></li>
</ul>
<p>最快解法， 直接获取所有能拿到的利润即可</p>
<pre><code class="language-python"><div>  <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        <span class="hljs-keyword">return</span> sum([i-j <span class="hljs-keyword">for</span> i,j <span class="hljs-keyword">in</span> zip(prices[<span class="hljs-number">1</span>:], prices[:<span class="hljs-number">-1</span>]) <span class="hljs-keyword">if</span> i&gt;j])  
</div></code></pre>
<p>tushare roy解法</p>
<pre><code><code><div>class Solution:
    def maxProfit(self, prices: List[int]) -&gt; int:
        n = len(prices)
        dp = [0] * (n+1)  
        maxdif = -float('inf')
        for j in range(1, n+1):
            dp[j] = max(dp[j-1], prices[j-1] + maxdif)
            maxdif = max(maxdif, dp[j] - prices[j-1])
        return dp[n]
</div></code></code></pre>
<p>labuladong公式解法， 无限次数， k和k-1 等同，所以把前面的公式里面的k去掉了。</p>
<pre><code class="language-python"><div>        <span class="hljs-comment"># dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-1] - PRICES[i])</span>
        <span class="hljs-comment"># dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i])</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        
        dp1 = [-float(<span class="hljs-string">'inf'</span>)] * (n+<span class="hljs-number">1</span>) 
        dp0 = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            dp1[i] = max(dp1[i<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-1</span>] - prices[i<span class="hljs-number">-1</span>])
            dp0[i] = max(dp0[i<span class="hljs-number">-1</span>], dp1[i<span class="hljs-number">-1</span>] + prices[i<span class="hljs-number">-1</span>])
        
        <span class="hljs-keyword">return</span> dp0[n]
</div></code></pre>
<h2 id="123-best-time-to-buy-and-sell-stock-iii-买2次">123. Best Time to Buy and Sell Stock III   买2次</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/</a></li>
</ul>
<p>tushare roy解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        m = len(prices)
        n = <span class="hljs-number">2</span>
        dp = [[<span class="hljs-number">0</span>] * (m+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            maxdif = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
                dp[i][j] = max(dp[i][j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
                maxdif = max(maxdif, dp[i<span class="hljs-number">-1</span>][j] - prices[j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> dp[n][m]
</div></code></pre>
<p>labuladong 解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        k = <span class="hljs-number">2</span>
        n = len(prices)
        dp0 = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>+k)]           <span class="hljs-comment"># without stock </span>
        dp1 = [[-float(<span class="hljs-string">'inf'</span>)] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>+k)] <span class="hljs-comment"># with stock</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                dp0[i][j] = max(dp0[i][j<span class="hljs-number">-1</span>], dp1[i][j<span class="hljs-number">-1</span>] + prices[j<span class="hljs-number">-1</span>])
                dp1[i][j] = max(dp1[i][j<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] - prices[j<span class="hljs-number">-1</span>])
                    
        <span class="hljs-keyword">return</span> dp0[k][n]
    
</div></code></pre>
<h2 id="188-best-time-to-buy-and-sell-stock-iv-买k次">188. Best Time to Buy and Sell Stock IV    买k次</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/</a></li>
</ul>
<p>tushare roy解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, k: int, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        <span class="hljs-keyword">if</span> k &gt;= n // <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> sum([i - j <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> zip(prices[<span class="hljs-number">1</span>:], prices[:<span class="hljs-number">-1</span>]) <span class="hljs-keyword">if</span> i &gt; j])
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            maxdif = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                maxdif = max(maxdif, dp[i<span class="hljs-number">-1</span>][j] - prices[j<span class="hljs-number">-1</span>])
                dp[i][j] = max(dp[i][j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
            
        <span class="hljs-keyword">return</span> dp[k][n]
</div></code></pre>
<p>labuladong 解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, k: int, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        <span class="hljs-keyword">if</span> k &gt;= n // <span class="hljs-number">2</span>:
            <span class="hljs-keyword">return</span> sum([i - j <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> zip(prices[<span class="hljs-number">1</span>:], prices[:<span class="hljs-number">-1</span>]) <span class="hljs-keyword">if</span> i &gt; j])
        
        dp0 = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k+<span class="hljs-number">1</span>)]
        dp1 = [[-float(<span class="hljs-string">'inf'</span>)] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(k+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, k+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                dp0[i][j] = max(dp0[i][j<span class="hljs-number">-1</span>], dp1[i][j<span class="hljs-number">-1</span>] + prices[j<span class="hljs-number">-1</span>])
                dp1[i][j] = max(dp1[i][j<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] - prices[j<span class="hljs-number">-1</span>])
                    
        <span class="hljs-keyword">return</span> dp0[k][n]
</div></code></pre>
<h2 id="309-best-time-to-buy-and-sell-stock-with-cooldown-不限次数有cooldown-sell之后要间隔至少一天才能继续buy">309. Best Time to Buy and Sell Stock with Cooldown  不限次数，有cooldown, sell之后要间隔至少一天才能继续buy</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/">https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/</a></li>
</ul>
<p>tushare roy解法, 在122题目的基础上，修改一个数字即可。</p>
<pre>
    dp[j] = max(dp[j-1], prices[j-1] + maxdif)
    maxdif = max(maxdif, dp[j-<font color="red">2</font>] - prices[j-1])
</pre>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        dp = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)  + [<span class="hljs-number">0</span>]
        maxdif = -float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            dp[j] = max(dp[j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif)
            maxdif = max(maxdif, dp[j<span class="hljs-number">-2</span>] - prices[j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> dp[n]
    
</div></code></pre>
<p>labuladong 解法, 在122题目的基础上，修改一个数字即可。</p>
<p>122 的公式</p>
<pre>
        # dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i])
        # dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-1] - PRICES[i])
</pre>
<p>309的公式</p>
<pre>
        # dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i])
        # dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-<font color="red">2</font>] - PRICES[i])
</pre>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int])</span> -&gt; int:</span>
        n = len(prices)
        dp0 = [<span class="hljs-number">0</span>] *(n+<span class="hljs-number">1</span>)
        dp1 = [-float(inf)] *(n+<span class="hljs-number">1</span>) + [-float(<span class="hljs-string">'inf'</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            dp0[i] = max(dp0[i<span class="hljs-number">-1</span>], dp1[i<span class="hljs-number">-1</span>] + prices[i<span class="hljs-number">-1</span>])
            dp1[i] = max(dp1[i<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-2</span>] - prices[i<span class="hljs-number">-1</span>]  )
            
        <span class="hljs-keyword">return</span> dp0[n]
</div></code></pre>
<h2 id="714-best-time-to-buy-and-sell-stock-with-transaction-fee">714. Best Time to Buy and Sell Stock with Transaction Fee</h2>
<p>tushare roy的解法, 在122题目的基础上，增加fee即可。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int], fee: int)</span> -&gt; int:</span>
        n = len(prices)
        dp = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)  
        maxdif = -float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            dp[j] = max(dp[j<span class="hljs-number">-1</span>], prices[j<span class="hljs-number">-1</span>] + maxdif - fee)
            maxdif = max(maxdif, dp[j] - prices[j<span class="hljs-number">-1</span>])
        <span class="hljs-keyword">return</span> dp[n]
    
</div></code></pre>
<p>labuladong 算法, 在122题目的基础上，增加fee即可。</p>
<p>122 的公式</p>
<pre>
        # dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i])
        # dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-1] - PRICES[i])
</pre>
<p>714的公式</p>
<pre>
        # dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i])
        # dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-1] - PRICES[i] - <font color="red">fee</font>)
</pre>
<p>或者</p>
<pre>
        # dp_without_stock[i] = max(dp_without_stock[i-1], dp_with_stock[i-1] + PRICES[i] - <font color="red">fee</font>)
        # dp_with_stock[i]    = max(dp_with_stock[i-1], dp_without_stock[i-1] - PRICES[i] )
</pre>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProfit</span><span class="hljs-params">(self, prices: List[int], fee: int)</span> -&gt; int:</span>
        n = len(prices)
        dp0 = [<span class="hljs-number">0</span>] *(n+<span class="hljs-number">1</span>)
        dp1 = [-float(inf)] *(n+<span class="hljs-number">1</span>) 
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            dp0[i] = max(dp0[i<span class="hljs-number">-1</span>], dp1[i<span class="hljs-number">-1</span>] + prices[i<span class="hljs-number">-1</span>] )
            dp1[i] = max(dp1[i<span class="hljs-number">-1</span>], dp0[i<span class="hljs-number">-1</span>] - prices[i<span class="hljs-number">-1</span>] -fee )
            
        <span class="hljs-keyword">return</span> dp0[n]
</div></code></pre>

    </body>
    </html>